Not Applicable
Communcations networks, such as B-ISDN networks, may support large volumes of traffic and offer a wide variety of services. The ever increasing traffic loads and the growing reliance on the telecommunications infrastructure for both business and personal communication necessitate reliable networks. In connection oriented networks, fast connection restoration after failure is a crucial element of reliability. Self-healing methods, which automatically restore network connections after failure, exist for general network architectures and for ring networks. These methods typically rely on distributed control to insure fast fault recovery and to protect against catastrophic failure.
Self-Healing Rings (SHRs) have proven to be an effective architecture for delivering protected SONET service. This architecture consists of 2- or 4-fiber rings which give the ability to carry traffic in both the clockwise and the counter-clockwise direction. When a failure occurs in the ring, traffic is switched away from the failed ring segment. SHRs offer fast restoration after failure, 100% traffic recovery from single location failures and a simple add/drop multiplexer architecture for network access. SHRs rely on a type of self-healing called protection switching where a failed connection is automatically switched to a pre-established back-up connection. End-to-end path protection switching is used in SONET Dual-Fed Unidirectional Path Switched Rings (UPSRs). Bidirectional Line Switched Rings (BLSRs) use point-to-point line protection switching. In addition to SONET transport, SHRs are proposed for other connection oriented networks such as all-optical wavelength division multiplexed (WDM) networks and ATM LANs. The protection switching mechanisms developed for SONET SHRs are being adapted to other networks and network layers. For example, ATM layer protection schemes are proposed for SONET Rings carrying ATM traffic and for ATM LANs.
Self-healing protocols usually involve four steps: spare capacity allocation, failure detection, failure notification and protection switching. One of the critical issue""s in determining the feasibility of a SHR protection mechanism is the required capacity needed to provide 100% restoration after single location failures. The ring capacity requirement depends on the spare bandwidth allocation, the traffic demand pattern, the protection scheme and the routing method. Traditionally, SONET connections are bidirectional and symmetric; in other words, a SONET link between two points in the network contains the same bandwidth allocation in both directions. Standards are being developed which allow SONET connections to be unidirectional or bidirectional asymmetric. Asymmetric connections contain different bandwidth allocations for each direction of a duplex path. Since asymmetric connections are possible in ATM as well, the traffic demand patterns in future SHRs may contain asymmetric demand between node pairs.
Three distinct methods of protection switching have been identified for ring networks. They are referred to here as 1:1 path switching, 1+1 path switching, and 1:1 line switching. FIG. 1a illustrates 1+1 path switching. The ring on the right demonstrates a protection switch. This method duplicates traffic entering the ring and dual-feeds it along both a working path and a protection path. The destination node chooses a path based on path status information. In SONET, a path is an STS or a VT.
In ATM, a path can be a VP group, a VP or a VC.
FIG. 1b illustrates 1:1 path switching wherein the dotted line represents the protection path. The source node transmits traffic along the working path only. When a fault is detected in the ring, failure messages are propagated to the source nodes of all affected paths. The source nodes switch the working paths to the protection paths traveling the opposite direction around the ring.
The third method, 1:1 line switching, does not switch traffic on an individual path basis; rather, the node upstream of the failure reroutes all traffic in a bundled fashion away from the failure. FIG. 1c illustrates one embodiment of a switching method where the destination nodes receive connections from either link. This method, commonly referred to as Kajiyama""s line method, uses only one loopback for switched traffic. The line switching mechanism in SONET rings results in a double loopback because a particular connection can only be received from one link.
These protection methods work for unidirectional or bidirectional rings. In a unidirectional ring all working traffic travels the same direction around the ring, and all protection traffic travels the opposite direction. Thus, working traffic is dedicated to one fiber, and two paths of a duplex connection contain a disjoint set of intermediate nodes.
In bidirectional rings, working traffic may be assigned to fibers in both directions. In general, each direction of a duplex connection traverses the same ring nodes but on different fibers.
It is possible to develop expressions for the required capacity for the ring size needed to support a particular traffic demand. In developing such expressions, all links on all fibers of a ring are assumed to have the same link rate; e.g., OC-12, etc. The size of the ring, or, similarly, the amount of traffic that can be placed on the ring, is determined by the required capacity for a particular set of connections. The required capacity is given by the maximum of the minimum bandwidth needed on any link to support a particular traffic pattern under a non-failure or any single location failure scenario. The bandwidth of this link, the maximum bandwidth link, gives the required capacity or minimum ring size needed to fully protect the traffic. The required capacity depends upon the traffic demand pattern, the protection scheme, the routing method and the spare capacity allocation method.
As mentioned above, the ring may be unidirectional or bidirectional. The ring type, which is determined by the routing method, impacts the required capacity. Another factor which impacts the required capacity is whether the demand between node pairs is symmetric or asymmetric. An analysis for the required capacity for the three protection schemes on unidirectional and bidirectional rings with symmetric and asymmetric demand.
In 1+1 path switching there is no routing choice since both paths from source to destination are active. The 1+1 path switching scheme is considered a unidirectional ring. (Typically, the default working paths are designated to one particular fiber.) The working paths may be assigned in a bidirectional sense where the working paths of a duplex connection traverse the same nodes but on opposite ring fibers; however, this distinction between working and protection paths does not affect the required capacity. For symmetric duplex connections, the dual-fed property of this protection scheme causes one direction of the demand between node pairs to be present on each link of the ring. Thus, if d(i, j) represents the one-way demand bandwidth between node pairs i and j, the required capacity, RC, is given by:                               R          ⁢                      xe2x80x83                    ⁢          C                =                              ∑                          one              ⁢                              xe2x80x83                            ⁢              way                                ⁢                      d            ⁡                          (                              i                ,                j                            )                                                          (        1        )            
For asymmetric connections, the bandwidth demand on each link may vary. The ring capacity is given by the link with the maximum bandwidth. A simple analysis of the 1+1 path switched ring indicates that simplex demand combinations on one fiber may require more bandwidth than combinations on the other fiber. This is illustrated in FIG. 2. The thin line represents a connection requiring d bandwidth. The thick line represents a connection requiring d+m bandwidth. Although the extra bandwidth m is available between nodes 1 and 4 on the outer fiber, using this bandwidth for a connection other than between nodes 1 and 4 results in an overlap on the inner fiber of the new connection with the d+m connection. The dotted line in FIG. 2 represents the new connection. The required capacity is d+2m as defined by the inner links between nodes 2 and 4.
The 1:1 protection methods are suitable for both unidirectional and bidirectional rings. Because these methods have only one active path between the source and destination, a routing choice exists for each connection. In 1:1 path and 1:1 line switching in a unidirectional ring, the working fiber contains the same topology as the working fiber in 1+1 path switching. The only difference is that the protection fiber contains no traffic; it contains only the traffic from the failed span after the protection switch. (This difference may be significant because the bandwidth is available for use by non-protected class of traffic.) Thus, for symmetric connections on a unidirectional ring, the required capacity for the 1:1 protection schemes is given by equation (1) above.
For asymmetric connections, however, a bandwidth advantage may exist for the 1:1 protection methods over 1+1 path switching. As shown in FIG. 2, the outer (working) fiber needs d+m bandwidth to support the connections. This working fiber determines the required capacity for 1:1 protection, whereas 1+1 path switching requires d+2m capacity on the inner fiber. Thus, on average, the 1:1 protection methods in unidirectional rings require equal or less capacity than 1+1 path protection for all demand patterns.
Bidirectional rings, such as SONET rings, may contain either 2 or 4 fibers. Four-fiber rings reserve a fiber in each direction for protection traffic. Two-fiber bidirectional rings reserve a portion of the bandwidth on each fiber for protection traffic. Existing 2-fiber rings reserve 50% of the bandwidth on each link for protection traffic. This spare bandwidth allocation factors into the ring capacity calculation. The link containing the maximum working traffic bandwidth for a given demand pattern is used as the maximum bandwidth link. The ring capacity is given by twice this bandwidth. The ring capacity for any demand pattern is the same for 1:1 path switching and 1:1 line switching even though the two methods produce different protection paths for the same working traffic. The working traffic alone determines the ring capacity because there is always enough spare bandwidth to reroute the maximum bandwidth link""s working traffic.
The present inventors have recognized that each bidirectional ring with 1:1 path protection may be designed using minimum spare bandwidth allocation methods to produce the smallest ring capacity requirement for any traffic demand pattern. Such minimum spare bandwidth methods may be adapted for use in a connection admission controlled method for minimum spare bandwidth allocation. To this end, the present inventors have examined the required ring size for three self-healing mechanisms under symmetric and asymmetric demand and different routing schemes. They have shown that asymmetric connections adversely affect 1+1 path switching when compared to 1:1 protection switching on unidirectional rings. This in turn allows the 1:1 methods to require a smaller unidirectional ring size. Similarly, their analysis of past bandwidth allocation methods on bidirectional rings which reserve 50% of the total bandwidth on each span for protection traffic show that the relative capacity of the protection methods are dependent on the demand pattern. The proposed minimum spare bandwidth assignments for the 1:1 protection methods, however, decrease the required capacity of bidirectional rings for both symmetric and asymmetric traffic. This optimal partitioning of working and protection bandwidth makes a bidirectional ring with 1:1 path switching the most bandwidth efficient method for all demand patterns.
The present invention provides for a method for reserving spare bandwidth for a link in a communication network including a plurality of links. The method provides for monitoring the volume of traffic routed through each link of the communication network. A single link failure for each link is then simulated and the volume of traffic which would be rerouted through each link for maintaining communication and the volume of traffic removed from each link are determined for each simulated single link failure. The difference between the volume of traffic which would need to be rerouted through each link and the corresponding volume of traffic removed from each link is then computed, and a maximum difference value is determined for each link for all simulated single link failures. An amount of spare bandwidth equivalent to the determined maximum difference is then reserved for each link.
In an alternative embodiment a connection admission control method for use in a communication network is provided. The method provides for the receipt of a request for a communication connection. The bandwidth needed for the requested communication and the maximum additional spare bandwidth needed is determined and the sum of the two is compared to the available bandwidth for each of the links. If sufficient bandwidth for each of the links is available, the communication request is accepted.